﻿using FittyWars.MathUtil;
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Drawing.Drawing2D;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace FittyWars.BordUtils
{
    #region Polygon
    public class Polygon
    {
        public List<Vector> Vectors { get; set; }
        public Polygon(List<Vector> v)
        {
            Vectors = v;
        }
    }
    #endregion
    
    #region Circle
    public class Circle
    {
        public Vector Center { get; set; }
        public float Radious { get; set; }
        public Circle()
        {
            Center = new Vector(0, 0);
            Radious = 0.0f;
        }

        public Circle(float radious)
        {
            Center = new Vector(0, 0);
            Radious = radious;
        }

        public Circle(Vector v, float radious)
        {
            Center = v;
            Radious = radious;
        }
    }
    #endregion

    #region Segment
    public class Segment
    {
        public Vector Start {get; set;}
        public Vector End {get; set;}

        public bool IsSegIntesect(Segment other)
        {
            if (
                (Start.X <= other.Start.X && other.Start.X <= End.X) ||
                (Start.X <= other.End.X && other.End.X <= End.X) ||
                (other.Start.X <= Start.X && Start.X <= other.End.X) ||
                (other.Start.X <= End.X && End.X <= other.End.X) 
               )
            { 
                return true; 
            }
            return false;
        }
    }
    #endregion

    public static class MathHelper
    {
        #region ElzingaHearn
        /// <summary>
        /// This algorithm can find the smallest circle containing a number of points
        /// http://delphiforfun.org/programs/circle_covering_points.htm
        /// 
        /// algorithem description :
        /// ---------------------------------------
        /// 1.  Choose any two points, Pi and Pj 
        /// 
        /// 2.  Construct the circle whose center is at the midpoint of the line connecting Pi and Pj and which passes through Pi and Pj.  
        ///     If this circle contains all points, then the center of the circle is the optimal X. 
        ///     Otherwise, choose a point Pk outside the circle.  
        ///     
        /// 3.  If the triangle determined by Pi, Pj and Pk is a right triangle or an obtuse triangle, 
        ///     rename the two points opposite the right angle or the obtuse angle as Pi and Pj  and go to step 2.  
        ///     Otherwise, the three points determine an acute triangle. 
        ///     Construct the circle passing through the three points. 
        ///     (The center is the intersection of the perpendicular bisectors of two sides of the triangle.) 
        ///     If the circle contains all the points, stop, else, go to 4.
        ///     
        /// 4.  Choose some point Pl not in the circle, and let Q be the point among {Pi, Pj, Pk} that is greatest distance from Pl. 
        ///     Extend the diameter (from the circle center) through the point Q into a line that divides the plane into two half planes. 
        ///     Let the point R be the point among {Pi, Pj, Pk} that is in the half plane opposite Pl. 
        ///     With the points Q, R, and Pl, go to step 3. 
        /// </summary>
        /// <param name="vectors"> The number of points </param>
        /// <returns> The smallest circle </returns>

        //public static StringBuilder sb = new StringBuilder();
        public static Circle ElzingaHearn(List<Vector> vectors)
        {
            //sb.Append(String.Format("ElzingaHearn Algorithm started\nElzingaHearn Algorithm started, Vectors :\n"));
            //foreach (Vector v in vectors){sb.Append(String.Format("({0},{1})\t", v[0].ToString("0.00"), v[1].ToString("0.00"))); }
            //sb.Append("\n\n");
            if(vectors.Count() < 1)
            {
                return null;
            }
            //sb.Append(String.Format("1.\tSelected\tpi = ({0},{1})\tpj = ({2},{3})\n\n", vectors.ElementAt(0)[0].ToString("0.00"), vectors.ElementAt(0)[1].ToString("0.00"), vectors.ElementAt(1)[0].ToString("0.00"), vectors.ElementAt(1)[1].ToString("0.00")));
            return ElzingaHearn_Step2(vectors, vectors.ElementAt(0), vectors.ElementAt(1));
        }
        private static Circle ElzingaHearn_Step2(List<Vector> vectors, Vector pi, Vector pj)
        {
            Circle ret = new Circle
            {
                Center = pi.Add(pj).Scale(0.5f),
                Radious = pi.Distance(pj) / 2
            };
            List<Vector> vectorsLeft = vectors.FindAll(v => (v != pi && v != pj));
            Vector outsider = vectorsLeft.FirstOrDefault(v => IsOutsideCircle(v, ret));
            if (outsider != null)
            {
                //sb.Append(String.Format("2.\tCreated Circle: ({0},{1}) , {2}\t\tpk = ({3},{4})\n\n", ret.Center[0].ToString("0.00"), ret.Center[1].ToString("0.00"), ret.Radious.ToString("0.00"), outsider[0].ToString("0.00"), outsider[1].ToString("0.00")));
                return ElzingaHearn_Step3(vectors, pi, pj, outsider);
            }
            //sb.Append(String.Format("2.\tCreated Circle: ({0},{1}) , {2} Finished!\n", ret.Center[0].ToString("0.00"), ret.Center[1].ToString("0.00"), ret.Radious.ToString("0.00")));
            return ret;
        }
        private static Circle ElzingaHearn_Step3(List<Vector> vectors, Vector pi, Vector pj, Vector pk)
        {
            var dict_pointToLength = new Dictionary<Vector,double>(){
                {pi,pj.Distance(pk)},
                {pj,pk.Distance(pi)},
                {pk,pi.Distance(pj)}
            };
            Vector acutePoint = dict_pointToLength.Keys.FirstOrDefault(
                key => 2 * dict_pointToLength[key] * dict_pointToLength[key] > dict_pointToLength.Values.Select(v => v * v).Sum()
                ); 

            if (acutePoint != null)
            {
                List<Vector> nonAcutePoint = dict_pointToLength.Keys.Where(key => key != acutePoint).ToList();
                //sb.Append(String.Format("3.\tTriangle Not-Acute\t\tpi = ({0},{1})\tpj = ({2},{3})\n\n", nonAcutePoint.ElementAt(0)[0].ToString("0.00"), nonAcutePoint.ElementAt(0)[1].ToString("0.00"), nonAcutePoint.ElementAt(1)[0].ToString("0.00"), nonAcutePoint.ElementAt(1)[1].ToString("0.00")));
                return ElzingaHearn_Step2(vectors, nonAcutePoint.ElementAt(0), nonAcutePoint.ElementAt(1));
            }
            Vector center = CircumCircleCenter(pi, pj, pk);
            Circle ret = new Circle{
                Center = center,
                Radious = center.Distance(pi)
            };
            List<Vector> vectorsLeft = vectors.FindAll(v => (v != pi && v != pj && v != pk));
            Vector outsider = vectorsLeft.FirstOrDefault(v => IsOutsideCircle(v, ret));
            if (outsider != null)
            {
                //sb.Append(String.Format("3.\tTriangle is Acute, Circle is ({0},{1}) , {2}\toutsider ({3},{4})\n\n", ret.Center[0].ToString("0.00"), ret.Center[1].ToString("0.00"), ret.Radious.ToString("0.00"), outsider[0].ToString("0.00"), outsider[1].ToString("0.00")));
                return ElzingaHearn_Step4(vectors, dict_pointToLength.Keys.ToList(), outsider, ret.Center);
            }
            //sb.Append(String.Format("3.\tTriangle is Acute, Circle is ({0},{1}) , {2}\tFinished !\n", ret.Center[0].ToString("0.00"), ret.Center[1].ToString("0.00"), ret.Radious.ToString("0.00")));
            return ret;
        }
        private static Circle ElzingaHearn_Step4(List<Vector> vectors, List<Vector> triangleVectors, Vector pl, Vector circumCenter)
        {
            Vector farest = triangleVectors.OrderByDescending(v => v.Distance(pl)).First();
            Vector otherSide = triangleVectors.Where(v => v != farest).Single(
                v => v.Subtract(circumCenter).Cross(farest.Subtract(circumCenter)) < 0
                );
            //sb.Append(String.Format("4.\tQ = ({0},{1})\tR = ({2},{3})\tPl = ({4},{5})", farest[0].ToString("0.00"), farest[1].ToString("0.00"), otherSide[0].ToString("0.00"), otherSide[1].ToString("0.00"), pl[0].ToString("0.00"), pl[1].ToString("0.00")));
            return ElzingaHearn_Step3(vectors, farest, otherSide, pl);        
        }

        private static Vector GetAcutePoint(Vector pi, Vector pj, Vector pk)
        {
            var dict_pointToLength = new Dictionary<Vector,double>(){
                {pi,pj.Distance(pk)},
                {pj,pk.Distance(pi)},
                {pk,pi.Distance(pj)}
            };
            return dict_pointToLength.Keys.FirstOrDefault(
                key => 2 * Math.Pow(dict_pointToLength[key],2) > dict_pointToLength.Values.Select(v => v * v).Sum()
                );
        }
        /// <summary>
        /// Find the center of tyhe circumcircle surrouning a triangle
        /// http://en.wikipedia.org/wiki/Circumscribed_circle#Circumcenter_Coordinates
        /// </summary>
        /// <param name="a">point in triangle</param>
        /// <param name="b">point in triangle</param>
        /// <param name="c">point in triangle</param>
        /// <returns>coordinates of center of circumcircle</returns>
        private static Vector CircumCircleCenter(Vector a, Vector b, Vector c)
        {
            double d = 2 * (a.X * (b.Y - c.Y) + b.X * (c.Y - a.Y) + c.X * (a.Y - b.Y));
            return new Vector(
                ( (Math.Pow(a.X,2) + Math.Pow(a.Y,2)) * (b.Y - c.Y) + (Math.Pow(b.X,2) + Math.Pow(b.Y,2)) * (c.Y - a.Y) + (Math.Pow(c.X,2) + Math.Pow(c.Y,2)) * (a.Y - b.Y) ) / d,
                ( (Math.Pow(a.X,2) + Math.Pow(a.Y,2)) * (c.X - b.X) + (Math.Pow(b.X,2) + Math.Pow(b.Y,2)) * (a.X - c.X) + (Math.Pow(c.X,2) + Math.Pow(c.Y,2)) * (b.X - a.X) ) / d
            );
        }
        #endregion

        private static bool IsOutsideCircle(Vector v, Circle c)
        {
            return v.Distance(c.Center) > c.Radious;
        }

        public static Polygon CreateRandomConvexedPoly(int seed, double rad)
        {
            Random rand = new Random(seed);
            int sides = 3 + rand.Next(4);
            double sector = 0.0;
            List<Vector> vectors = new List<Vector>();
            foreach (double d in RandomDoublesBySum(sides, seed))
            {
                vectors.Add(new Vector(
                rad * Math.Cos(2*Math.PI*(d + sector)),rad * Math.Sin(2*Math.PI*(d + sector))
                ));
                sector += d;
            }
            Circle c = ElzingaHearn(vectors);
            vectors = vectors.Select(v => new Vector(v.X - c.Center.X, v.Y - c.Center.Y)).ToList();
            return new Polygon(vectors);
        }

        public static List<double> RandomDoublesBySum(int amount, int seed)
        {
            List<double> res = new List<double>();
            Random rand = new Random(seed);
            double d, r;
            for (int i = 0; i < amount; i++)
            {
                if (res.Count() == 0)
                {
                    res.Add(1.0);
                    continue;
                }
                d = res.First();
                r = rand.NextDouble();
                res.Remove(d);
                res.Add(d * r);
                res.Add(d * (1 - r));
            }
            return res;
        }

        #region Polygon Intersection
        public static bool CheckSingleIntersection(Element e1, Element other)
        {
            double dist = e1.GetFutureCenter().Distance(other.Center);
            if (dist > e1.Radious + other.Radious )
            {
                return false;
            }
            if (e1.BodyParts == null)
            {
                if (other.BodyParts == null)
                {
                    return true;
                }
                else
                {
                    foreach (Polygon p in other.GetElementGeometrics())
                    {
                        if (IsCirclePolyInterset(new Circle(e1.GetFutureCenter(), e1.Radious), p))
                        {
                            return true;
                        }
                    }
                    return false;
                }
            }
            else
            {
                if (other.BodyParts == null)
                {
                    foreach (Polygon p in e1.GetElementFutureGeometrics())
                    {
                        if (IsCirclePolyInterset(new Circle(other.Center, other.Radious), p))
                        {
                            return true;
                        }
                    }
                    return false;
                }
            }
            foreach (Polygon p1 in e1.GetElementFutureGeometrics())
            {
                foreach (Polygon p2 in other.GetElementGeometrics())
                {
                    if (IsPolyPolyIntersect(p1, p2))
                    {
                        return true;
                    }
                }
            }
            return false;
        }


        public static bool IsPolyPolyIntersect(Polygon p, Polygon other)
        {
            List<Vector> directions = new List<Vector>();
            for (int i = 0; i < p.Vectors.Count(); i++)
            {
                if (i == 0)
                {
                    directions.Add(p.Vectors.ElementAt(0).Subtract(p.Vectors.ElementAt(p.Vectors.Count() - 1)));
                }
                else
                {
                    directions.Add(p.Vectors.ElementAt(i).Subtract(p.Vectors.ElementAt(i - 1)));
                }
            }
            for (int i = 0; i < other.Vectors.Count(); i++)
            {
                if (i == 0)
                {
                    directions.Add(other.Vectors.ElementAt(0).Subtract(other.Vectors.ElementAt(other.Vectors.Count() - 1)));
                }
                else
                {
                    directions.Add(other.Vectors.ElementAt(i).Subtract(other.Vectors.ElementAt(i - 1)));
                }
            }
            foreach (Vector d in directions)
            {
                Segment s1 = OrtographicProjection(p, d);
                Segment s2 = OrtographicProjection(other, d);
                if (!s1.IsSegIntesect(s2))
                {
                    return false;
                }
            }
            return true;
        }

        public static Segment OrtographicProjection(Polygon p, Vector d)
        {
                Matrix mat = new Matrix(
                    (d.Y * d.Y) / (d.Y * d.Y + d.X * d.X), 
                    (-d.X * d.Y) / (d.Y * d.Y + d.X * d.X), 
                    (-d.X * d.Y) / (d.Y * d.Y + d.X * d.X), 
                    (d.X * d.X) / (d.Y * d.Y + d.X * d.X), 
                    0, 0);
                List<Vector> projVectors = p.Vectors.Select(v => v.ApplyMatrix(mat)).ToList();
                return new Segment
                {
                    Start = projVectors.Find(v => v.X == projVectors.Min(u => u.X)),
                    End = projVectors.Find(v => v.X == projVectors.Max(u => u.X))
                };
        }

        public static bool IsCirclePolyInterset(Circle c, Polygon other)
        {
            foreach (Vector v in other.Vectors)
            {
                if (v.Distance(c.Center) < c.Radious)
                {
                    return true;
                }
            }
            return false;
        }
        #endregion
    }
}
